1. Field of the Invention
The present invention relates to communication networks and more specifically to network switches and associated switch to switch protocols which provide improved bandwidth utilization and load balancing in data processing communication networks having redundant paths between network devices.
2. Discussion of Related Art
It is common in present computing environments to connect a plurality of computing systems and devices through a communication medium often referred to as a network. Such networks among communicating devices permit devices (or users of devices) to easily exchange and share information among the various devices. The Internet is a presently popular example of such networking on a global scale. Individual users attach their computers to the Internet, thereby enabling sharing of vast quantities of data on other computers geographically dispersed throughout the world.
Networked computing systems may be configured and graphically depicted in a wide variety of common topologies. In other words, the particular configurations of network communication links (also referred to as paths) and devices between a particular pair of devices wishing to exchange information may be widely varied. Any particular connection between two computers attached to a network may be direct or may pass through a large number of intermediate devices in the network. In addition, there may be a plurality of alternative paths through the network connecting any two network devices. Present day computing networks are therefore complex and vary in their configurations and topologies.
Most present network communication media and protocols are referred to as packet oriented. A protocol or communication medium may be said to be packet oriented in that information to be exchanged over the network is broken into discrete sized packets of information. A block of information to be transferred over the network is decomposed into one or more packets for purposes of transmission over the network. At the receiving end of the network transmission, the packets are re-assembled into the original block of data.
In general, each packet includes embedded control and addressing information that identifies the source device which originated the transmission of the packet and which identifies the destination device to which the packet is transmitted. Identification of source and destination devices is by means of an address associated with each device. An address is an identifier which is unique within the particular computing network to identify each device associated with the network. Such addresses may be unique to only a particular network environment (i.e., a network used to interconnect a single, self-contained computing environment) or may be generated and assigned to devices so as to be globally unique in co-operation with networking standards organizations.
At the lowest level of network communication, such addresses are often referred to as MAC address (Media ACcess address). Network protocols operable above this lowest level of communication may use other addresses for other purposes in the higher level communication techniques. But in most network low level communication levels, operable on the physical link medium, an address is referred to as a MAC address.
In many present commercially available network environments, the network communication medium is in essence a bus commonly attached to a plurality of devices over which the devices exchange. In a simple networking topology, all devices may be attached to a such a bus structured common network medium. Any particular single network medium has a maximum data exchange bandwidth associated therewith. The maximum data exchange bandwidth of a medium is determined by a number of electrical and physical properties of the medium and protocols used to communicate over that medium. For example, a popular family of related network media and protocols are collectively referred to as Ethernet. Ethernet defines a standard protocol for the exchange of messages over the communication medium. A variety of communication media are also defined as part of the Ethernet family. The communication bandwidth of the Ethernet family of standards range from approximately 10 Mbit (million bits of information) per second to 1 Gbit per second. Therefore, a single (slow) Ethernet connection, for example, has a maximum data exchange bandwidth of approximately 10 Mbit per second.
In present network computing environments, a number of devices are used in addition to interconnected computing systems to efficiently transfer data over the network. Routers and switches are in general network devices which segregate information flows over various segments of a computer network. A segment, as used herein, is any subset of the network computing environment including devices and their respective interconnecting communication links. As noted above, a single computer network communication link has a maximum data transfer bandwidth parameter defining the maximum rate of information exchange over that network. Where all devices on a computer network share a common network medium, the maximum bandwidth of the computer network may be rapidly reached. The overall performance of the networked computing environment may be thereby reduced because information exchange requests may have to await completion of earlier information exchange requests presently utilizing the communication link.
It is often the case, however, that particular subsets of devices attached to the network have requirements for voluminous communication among members of the same subset but less of a requirement for information exchange with other devices outside their own subset. Though standard switch features generally do not include identifying such logical groupings of devices, some enhanced switching features do permit such logic to be performed within a switch device. For example, some enhanced switch features include the concept of defining and routing information based on virtual LAN (VLAN) definitions. In a VLAN, a group of devices may be defined as logically being isolated on a separate network although physically they are connected to a larger network of devices. VLAN features of enhanced switches are capable of recognizing such VLAN information and can route information appropriately so that devices in a particular VLAN are logically segregated from devices outside the VLAN.
For example, the financial department of a large corporation may have significant information exchange requirements within the financial department but comparatively insignificant needs for data exchange with other departments. Likewise, an engineering group may have significant needs for data exchange within members (computing systems and devices) of the same engineering group but not outside the engineering group. There may in fact be multiple of such subsets of devices in a typical computing network. It is therefore desirable to segregate such subsets of devices from one another so as to reduce the volume of information exchange applied to the various segments of the computer network.
In particular, a switch device is a device that filters out packets on the network destined for devices outside a defined subset (segment) and forwards information directed between computing devices on different segments of a networked computing environment. The filtering and forwarding of such information is based on configuration information within the switch that describes the data packets to be filtered and forwarded in terms of source and/or destination address information (once address locations are xe2x80x9clearnedxe2x80x9d by the switch(es)).
Network switch devices and protocols associated therewith are also used to manage redundant paths between network devices. Where there is but a single path connecting two network devices, that single path, including all intermediate devices between the source and destination devices, represent a single point of failure in network communications between that source and destination device. It is therefore common in network computing environments to utilize a plurality of redundant paths to enhance reliability of the network. Multiple paths between two devices enhances reliability of network communication between the devices by allowing for a redundant (backup) network path to be used between two devices when a primary path fails.
FIG. 1 shows an exemplary, simple networked computing environment in which multiple paths exist for communication between devices A 100, B 102, and C 104. These exemplary network devices are each attached to one of a plurality of switches (S1106, S2108, S3110, and S4112). Each device has multiple possible paths to each of the other two devices. For example, device A 100 may exchange information with device C 104 through any of three possible paths (via switches S1106 and S4112, respectively). The first exemplary path is a direct path connecting device A 100 directly to device C 104 through a port on switch S1106 and a port on switch S4112. A second path is through switch S1106 to switch S3110 and then through switch S4112. A third path is via switch S1106, switch S2108, and switch S4114. These three paths may be used as redundant communication paths connecting the two devices A 100 and C 104. Where a first path fails, the second path or third may be activated to assume responsibility for exchange of information between devices A and C. In like manner, there are three paths for communication between devices A 100 and B 102 and between devices B 102 and C 104.
Where redundant paths are available in such network computing environments, it remains a problem to effectively utilize the full available bandwidth. It would be desirable to utilize all redundant paths in parallel so as to increase the available communication bandwidth between two communicating devices. Where only a single path is used, the maximum bandwidth for exchange of information is limited to that of a single communication link. Where, on the other hand, all redundant links are used in parallel, the maximum communication bandwidth is increased by the number of links used in parallel. For example, as shown in FIG. 1, the communication bandwidth between any of the devices could, in theory, be increased by up to a factor of three.
However, as presently practiced in the art, protocols used among switch devices (e.g., S1106 through S4112) render such parallel communication paths unusable. Switches 105 through 112 as presently practiced in the art often use a protocol commonly referred to as xe2x80x9cspanning treexe2x80x9d to discover the existence of redundant communication paths as known to a network of switches. The spanning tree protocol is described in detail in a proposed IEEE standard P802.1p entitled Standard for Local and Metropolitan Area Networks Supplement to Media Access Control (MAC) Bridges. Traffic Class Expediting and Dynamic Multicast Filtering. 
The spanning tree protocol as implemented in switches broadcasts (more precisely multicasts) information from the switch out to all devices that recognize the selected multicast address connected to paths from the switch. A multicast message is one which is directed to all devices rather than to a particular destination address on the network. The information in the multicast message describes the address forwarding information known to that switch. From such information shared among all the switches, each switch can derive the various paths in the network. Each switch device so attached to the multicasting device receives the information and forwards (multicasts) the message to each device attached to it (except the path from which it directly received the message), and so on. If such a multicast message returns on a path to the originating device, a loop must exist among the paths connecting the various switches. To reduce the number of messages generated on the network by virtue of such multicast messages, the spanning tree protocol requires that redundant paths so discovered be disabled. In a large network without spanning tree protocol to disable redundant paths, received multicast messages can xe2x80x9ccascadexe2x80x9d from each receiving switch to all other attached switches. The volume of such cascading messages may grow rapidly or even exponentially. Such multicast messages exchanged among the switched may in fact require a substantial portion of the available communication bandwidth of the network. Such conditions are often referred to as xe2x80x9cbroadcast storms.xe2x80x9d
The spanning tree protocol therefore requires the disabling of redundant paths to avoid broadcast storms. Only when a path is known to have failed will a redundant path be enabled and used for the exchange of data. The spanning tree protocol therefore precludes aggregation of the available bandwidth to improve communication bandwidth by using multiple redundant paths in parallel. FIG. 2 is a block diagram of the same exemplary network of FIG. 1 where three communication links 114 between the switches have been disabled to prevent loops in the network and the resultant broadcast storm otherwise inherent in the spanning tree protocol.
Another problem with the spanning tree protocol arises from the fact that a preferred path may be unavailable due to the need to disable paths that cause loops among the switches. For example, as shown in FIG. 2, the preferred path between switches S1106 and S4112 may be the direct one which is disabled. To leave this direct communication link enabled would permit loops in the paths among the switches. Rather, a more circuitous route through switches S1, 106, S3110 and S4112 must be used to exchange information between switches S1106 and S4112. The spanning tree protocol does not assure that the best path between two switches will be left enabled. Rather, it merely attempts to assure that some path between switches is available, specifically, a relatively minimal path connecting all switchesxe2x80x94a spanning tree.
The spanning tree protocol therefore precludes maximizing use of available bandwidth in a network of switches.
Some switches have provided a partial solution to this problem by using a technique known as xe2x80x9ctrunking.xe2x80x9d Where there are multiple paths directly between two switches, the multiple paths serve as redundant communication paths but are trunked by the switches and treated logically as though they were a single path with higher maximum bandwidth. FIG. 3 is a block diagram of the same exemplary network environment of FIG. 2 wherein a plurality of communication paths between switch S1106 and S3110 are trunked. The communication path between switches S1106 and S3110 is therefore capable of using the trunked paths between them as though they were a single connection in terms of the spanning tree protocols. Since the redundant paths are treated as a single path for purposes of the spanning tree protocols, they need not be shut down to preclude broadcast storms.
However, trunking does not address the bandwidth issue in a broad sense. Rather, the trunking technique is only applicable where the multiple paths are between a particular pair of switches. The bandwidth limit is merely shifted from that of a single communication link to that of the number of communication links supported by a single switch.
It is a further problem that by precluding use of redundant links between switches, the spanning tree protocol also precludes the ability to balance communication loads among the redundant paths between switches. Where such multiple paths are allowed to simultaneously operate, it would be desirable for the switches to distribute the packet exchange communication among them over such multiple paths. Such distribution, often referred to as load balancing, further enhances the ability of the network to optimize the utilization of available throughput in the network of switches. Underutilized paths may be used to offload packet communication on overloaded paths.
It is therefore a problem in present networks of switches to simultaneously operate redundant paths between switches of the network to thereby maximize utilization of available bandwidth and to thereby communicate among the switches to balance communication loads over redundant paths.
In order to balance the loads over redundant paths, it is desirable to propagate cost information among switches of a network. A switch may, for example, detect that a particular path through the network of switches is heavily loaded with packets to be switched. Where the network topology and protocols permit, it would be desirable in such a case to redirect portions of the packet traffic handled by the overloaded switch to alternate paths less heavily loaded. Large network systems often have multiple alternate routes available for use to transmit packets from one switch to another.
It is generally known to use estimated costs associated with paths among the switches. However, as presently practiced in the art, such estimates represent poor models of actual performance of the path. Rather, estimated cost calculations as presently practiced are often fixed values. The estimated costs therefore do not respond to changes in the network traffic through the ports of the switches.
It is a particular problem to efficiently compute a meaningful cost value representative of the actual cost of passing a packet through a particular switch or more generally over a particular path. Further it is a problem to compute and estimate simply such that it may rapidly adapt to bursts in the switch path usage. It is evident from the above that a need exists for improved cost calculations to estimate the performance of paths in a switch network.
The present invention solves the above and other problems, thereby advancing the state of useful arts, by providing network switch devices and associated switch to switch protocols which permit the operation of multiple links throughout the network involving multiple switches, and which provide for improved utilization of the aggregate bandwidth of all paths in the network. Further, the present invention provides a technique for computing cost values for port/link performance which is at once simple and effective.
By permitting parallel use of all communication paths and switches in the network, the present invention improves scalability of network communication bandwidth as compared prior techniques. The aggregate bandwidth capability within the entire network may be increased by simply adding additional communication paths and associated switches.
In particular, the present invention includes a method for calculating a cost value associated with each path in the network. The cost calculation methods of the present invention are simple yet accurate in their modeling of performance factors in the path""s communication performance. The cost calculation methods of the present invention include two components: a latency component and a throughput component. The latency component provides an accurate estimate of the processing time required by a switch to process a received packet for purposes of forwarding it to its destination. The throughput component is a measure of the data transfer capability of the communication links along a path of the switch network.
The latency component computes a present latency value for an outbound port of a switch as the depth of the queue of outbound packets divided by the port speed. The weighted average is then computed from the present latency value and a number of previous latency values. The present latency and hence the weighted average are computed periodically within each switch. This outbound latency is then adjusted by a multiplication factor when the switch queue for the port is full and therefore packets are rejected or otherwise dropped by the switch. The latency component for an inbound port is computed in like manner except that the port speed used for the latency computation is that of the fastest port of the switch which returns to the originating switch of a packet. The queue depth used in computing outbound port latency is that of the port on which the packet was received. In computing the inbound port latency, the queue depth of the port on which the packet will be forwarded is used. In the preferred embodiment, the switch polls each of its ports to compute the updated latency therefore once per second.
The throughput component of a given path is computed as the speed of the slowest port (communication link) along the path.
The two components are combined into a port load factor as the ratio and throughput. The port load factor (a cost value) is propagated throughout the network of switches so as to inform all switches of the costs associated with transmissions on each port of each switch of the network. The port load factor (PLF) is then useful in each switch for selecting a preferred port for forwarding of a packet through a switch to an ultimate destination. The switch selects a port which will forward the packet toward the intended destination and which has the xe2x80x9cbestxe2x80x9d PLF value associated therewith. Where the PLF values are identical for multiple choices available to a switch, any of several xe2x80x9ctie breakingxe2x80x9d selection techniques may be employed. Preferably all switches employ the same tie breaking selection technique so as to minimize the potential for causing a packet to loop through the network switches.
In addition, the inbound link costs associated with a switch is added to all outbound costs propagated from that switch. This technique permits the cost estimation to rapidly adapt to overutilization of particular network paths due to bursty traffic.
Still further, the statistical estimation model used by the present invention is simple to compute as compared to prior techniques. The switch CPU can therefore re-compute the cost information estimates more frequently. The higher frequency calculation improves the accuracy of the estimates to more closely follow actual link performance including bursts of message traffic. Yet another advantage of the techniques of the present invention arise in computing the costs associated with a group port (i.e., trunked lines). The statistical model of the present invention simplifies modeling of the performance of the group port (i.e., trunked lines as a group) as well as the individual paths which comprise the group.
The above, and other features, aspects and advantages of the present invention will become apparent from the following descriptions and attached drawings.